import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 一个包含二叉树常用遍历操作的工具类。
 * 该类被声明为 final，因此不可被继承。
 * 私有构造函数防止该工具类被实例化。
 */
public final class TreeTraversalUtils {

    // 私有构造函数，防止实例化
    private TreeTraversalUtils() {
    }

    /**
     * 公共静态内部类，用于定义二叉树节点。
     * 可通过 TreeTraversalUtils.TreeNode 进行访问。
     */
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 公共静态内部类，为 BFS 写法三提供状态封装。
     */
    public static class State {
        public TreeNode node;
        public int depth;

        public State(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }


    // --- 深度优先搜索 (DFS) ---

    /**
     * 经典的递归遍历（DFS）框架。
     * 这是一个框架方法，在前、中、后序位置添加自己的逻辑。
     *
     * @param root 树的根节点
     */
    public static void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置 (Pre-order)
        // e.g., System.out.println("Pre-order: " + root.val);
        traverse(root.left);
        // 中序位置 (In-order)
        // e.g., System.out.println("In-order: " + root.val);
        traverse(root.right);
        // 后序位置 (Post-order)
        // e.g., System.out.println("Post-order: " + root.val);
    }


    // --- 广度优先搜索 (BFS) ---

    /**
     * BFS 写法一：最简单的层序遍历。
     * 按照从上到下、从左到右的顺序访问所有节点。
     *
     * @param root 树的根节点
     */
    public static void levelOrderSimple(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();

            // 在此处处理节点 cur，例如打印
            // System.out.println(cur.val);

            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }

    /**
     * BFS 写法二：可以记录并区分层数的层序遍历。
     * 这是最常用的写法，常用于需要按层处理的场景。
     *
     * @param root 树的根节点
     * @return 一个列表，其中每个元素是代表一层所有节点值的列表。
     */
    public static List<List<Integer>> levelOrderWithDepth(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int levelSize = q.size();
            List<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode cur = q.poll();
                currentLevel.add(cur.val);

                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }

    /**
     * BFS 写法三：使用 State 对象，最灵活的层序遍历框架。
     * 适用于每个节点需要携带额外状态（如深度、路径和等）的复杂场景。
     *
     * @param root 树的根节点
     */
    public static void levelOrderWithStateObject(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<State> q = new LinkedList<>();
        q.offer(new State(root, 1)); // 根节点深度为 1

        while (!q.isEmpty()) {
            State currentState = q.poll();
            TreeNode curNode = currentState.node;
            int currentDepth = currentState.depth;

            // 在此处处理节点 curNode 和它的状态 currentState
            // e.g., System.out.println("Depth: " + currentDepth + ", Val: " + curNode.val);

            if (curNode.left != null) {
                q.offer(new State(curNode.left, currentDepth + 1));
            }
            if (curNode.right != null) {
                q.offer(new State(curNode.right, currentDepth + 1));
            }
        }
    }
}